package _66_机器人的运动范围;

/*
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），
因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
 */
public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        boolean[][] visited = new boolean[rows][cols];

        return s(threshold,rows,cols, 0, 0, visited);
    }

    int s(int threshold, int rows, int cols, int m, int n, boolean[][] visited) {

        int i = m, j = n;

        if (i < 0 || j < 0 || i >= rows || j >= cols ||visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;

        int sum = 0;
        while (i > 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j > 0) {
            sum += j % 10;
            j /= 10;
        }

        if (sum > threshold) return 0;


        int count = 1;
        count+=s(threshold,rows,cols, m+1, n, visited);
        count+=s(threshold,rows,cols, m-1, n, visited);
        count+=s(threshold,rows,cols, m, n+1, visited);
        count+=s(threshold,rows,cols, m, n-1, visited);
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.movingCount(10,1,100));
    }
}
